package pr2012.practico4.grafos;

public class TGrafoDirigido implements IGrafoDirigido {

	private TLista vertices = new TLista();
//	private TRecorrido recorrido = new TRecorrido();
	
	@Override
	public boolean insertarVertice(Comparable unaEtiqueta) {
		if (buscarVertice(unaEtiqueta) != null){
			return false;
		}
		TVertice vert = new TVertice(unaEtiqueta);
		TElemento elem = new TElemento(unaEtiqueta, vert);
		vertices.insertarAlFinal(elem);
		return true;
	}
	
	public TVertice buscarVertice(Comparable unaEtiqueta) {
		TElemento elem = (TElemento) vertices.buscarEtiqueta(unaEtiqueta);
		if (elem != null)
			return (TVertice) elem.datos;
		return null;
	}

	@Override
	public boolean existeVertice(Comparable unaEtiqueta) {
		 return (this.vertices.buscarEtiqueta(unaEtiqueta) != null);
	}

	@Override
	public boolean insertarAdyacencia(Comparable etiquetaOrigen, Comparable etiquetaDestino, Comparable costo) {
		TVertice origen = this.buscarVertice(etiquetaOrigen);
		TVertice destino = this.buscarVertice(etiquetaDestino);
		if ((origen != null) && (destino != null)){
			return origen.insertarAdyacencia(destino, costo);
		}else{
			return false;
		}
	}

	@Override
	public boolean existeAdyacencia(Comparable etiquetaOrigen,	Comparable etiquetaDestino) {
		TElemento elem = (TElemento) vertices.buscarEtiqueta(etiquetaOrigen);
		if (elem != null){
			TVertice vert = (TVertice) elem.datos;
			if (vert.buscarAdyacencia(etiquetaDestino) != null){
				return true;
			}
		}
		return false;
	}

	@Override
	public boolean eliminarVertice(Comparable nombreVertice) {
		TElemento actual =this.vertices.primero;
		while (actual!=null){
			eliminarAdyacencia(actual.etiqueta,nombreVertice);
			actual=actual.siguiente;
		}
		return this.vertices.eliminarEtiqueta(nombreVertice);
	}	

	@Override
	public boolean eliminarAdyacencia(Comparable nomVerticeOrigen, Comparable nomVerticeDestino) {
		 TVertice a = this.buscarVertice(nomVerticeOrigen);
         return a.eliminarAdyacencia(nomVerticeDestino);
	}
	
	@Override
	public TRecorrido bpf(Comparable etiquetaOrigen) {
		TRecorrido recorrido = new TRecorrido();
		TElemento elem =  vertices.buscarEtiqueta(etiquetaOrigen);
		TElemento elem2 =  vertices.buscarEtiqueta(etiquetaOrigen);
		TVertice unVertice = (TVertice) elem.datos;
		TVertice actual=(TVertice) elem2.datos;
		while (actual!=null){
			if (actual.visitado=true){
				actual.visitado=false;
			}
			actual=actual.siguienteAdyacente(actual);
		}
		return unVertice.bpf(recorrido);
	}

	@Override
	public TRecorrido bea(Comparable etiquetaOrigen) {
		TRecorrido recorrido = new TRecorrido();
		TLista cola = new TLista();
		TElemento elem = vertices.buscarEtiqueta(etiquetaOrigen);
		TElemento elem2 =  vertices.buscarEtiqueta(etiquetaOrigen);
		TVertice unVertice = (TVertice) elem.datos;
		TVertice actual=(TVertice) elem2.datos;
		while (actual!=null){
			if (actual.visitado=true){
				actual.visitado=false;
			}
			actual=actual.siguienteAdyacente(actual);
		}
		return unVertice.bea(recorrido,cola);
	}

	@Override
	public TCaminos todosLosCaminos(Comparable etiquetaOrigen,
			Comparable etiquetaDestino) {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public boolean[][] warshall() {
		return null;
		
		/*
		int cantidadVertices = vertices.obtenerCantidadElementos();
        Integer[][] matrizCostos = obtenerMatrizCostos();
        boolean[][] matrizWarshall = new boolean[cantidadVertices][cantidadVertices];
        for (int i = 0; i < matrizCostos.length; i++) 
        {
                for (int j = 0; j < matrizCostos.length; j++) 
                {
                        matrizWarshall[i][j] = (matrizCostos[i][j]!=null);
                }
        }
        return matrizWarshall;
        
        
        
		//
		int cantidadVertices = vertices.obtenerCantidadElementos();
		Integer[][] matrizCostos = obtenerMatrizCostos();
		boolean[][] matrizWarshall = new boolean[cantidadVertices][cantidadVertices];
		for (int i = 0; i < matrizCostos.length; i++){
			for (int j = 0; j < matrizCostos.length; j++){
				matrizWarshall[i][j] = (matrizCostos[i][j]!=null);
				if (j == i){
					matrizWarshall[i][j] = true;
				}
			}
		}
		for (int k = 0; k < matrizCostos.length; k++){
			for (int i = 0; i < matrizCostos.length; i++){
				for (int j = 0; j < matrizCostos.length; j++){
					if (!matrizWarshall[i][j]){
						matrizWarshall[i][j] = (matrizWarshall[i][k] && matrizWarshall[k][j]);
					}
				}
			}
		}
		return matrizWarshall;﻿
		 */ 

	}

	@Override
	public TElementoFloyd floyd() {
		// TODO Auto-generated method stub
		return null;
	}
	
	/*
	public Integer[][] floyd(){
		Integer[][] matrizCostos = obtenerMatrizCostos();
		for (int k = 0; k < matrizCostos.length; k++) {
			for (int i = 0; i < matrizCostos.length; i++) {
				for (int j = 0; j < matrizCostos.length; j++) {
					if ((i != k)&&(k != j)&&(i!=j)){
						if ((matrizCostos[i][k] != null)&&(matrizCostos[k][j]!= null)){
							int costoIK = matrizCostos[i][k].intValue();
							int costoKJ = matrizCostos[k][j].intValue();
							int costoIJ = Integer.MAX_VALUE;
							if (matrizCostos[i][j] != null){
								costoIJ = matrizCostos[i][j].intValue();
							}
							matrizCostos[i][j] = Math.min(costoIJ, costoIK + costoKJ);
						}
					}
				}
			}
		}
		return matrizCostos;
	}
	*/

	@Override
	public Comparable centroDelGrafo() {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public TElementoDijkstra dijkstra(Comparable etiquetaOrigen) {
		// TODO Auto-generated method stub
		return null;
	}
	
//	public int[] dijkstra(int[][] matrizCostos) {
//		boolean sinProcesar[] = new boolean[matrizCostos.length];
//		sinProcesar[0] = false;
//		for (int i = 1; i < sinProcesar.length; i++) {
//			sinProcesar[i] = true;
//		}
//		int caminoMinimos[] = new int[matrizCostos.length];
//		caminoMinimos[0] = 0; // la distancia del origen al origen, es 0
//		// Establecemos la distancia desde el vértice 0 a los demás vértices.
//		for (int i = 1; i < caminoMinimos.length; i++)
//			caminoMinimos[i] = matrizCostos[0][i];
//		int verticeSinCamino = 0;
//		// Recorremos desde el primer vértice hasta el penúltimo.
//		for (int i = 0; i < (sinProcesar.length - 2); i++) {
//			// No tiene sentido calcular la distancia desde 0 hasta 0,
//			// comenzamos en 1
//			int contador = 1;
//			// Buscamos el primer vértice al que no se le haya calculado el
//			// camino mínimo
//			while (!sinProcesar[contador])
//				contador++;
//			verticeSinCamino = contador;
//			// Comprobamos que el vértice elegido tenga la menor distancia al
//			// origen.
//			for (contador++; contador < sinProcesar.length; contador++) {
//				/*
//				 * Si el vértice está sin procesar Y la distancia al origen del
//				 * vértice actual es mayor que la del nuevo entonces, pasamos a
//				 * tratar el nuevo por estar a menor distancia.
//				 */
//				if (sinProcesar[contador]
//						&& caminoMinimos[verticeSinCamino] >
//				caminoMinimos[contador])
//					verticeSinCamino = contador;
//			}
//			// El vértice ya está procesado!
//			sinProcesar[verticeSinCamino] = false;
//			// Actualizamos las distancias al origen comprobando las uniones que
//			// tiene el vértice procesado.
//			for (contador = 1; contador < sinProcesar.length; contador++) {
//				/*
//				 * Si el vértice no ha sido procesado Y la distancia actual al
//				 * origen es mayor que la que habría pasando por el vértice
//				 * recien procesado entonces, actualizamos la distancia mínima.
//				 */
//				if (sinProcesar[contador]
//						&& (caminoMinimos[contador] >
//						(caminoMinimos[verticeSinCamino] + matrizCostos[verticeSinCamino][contador])))
//					caminoMinimos[contador] = caminoMinimos[verticeSinCamino]
//							+ matrizCostos[verticeSinCamino][contador];
//			}
//		}
//		return caminoMinimos;
//	}

	@Override
	public boolean tieneCiclos() {
		// TODO Auto-generated method stub
		return false;
	}
	
	/*
	public Integer[][] obtenerMatrizCostos(){
		int cantidadVertices = vertices.obtenerCantidadElementos();
		Integer[][] matrizCostos = new Integer[cantidadVertices][cantidadVertices];
		int i = 0;
		TElemento elemVerticeI = (TElemento) vertices.obtenerPrimero();
		while(elemVerticeI != null){
			int j = 0;
			TElemento elemVerticeJ = (TElemento) vertices.obtenerPrimero();
			while(elemVerticeJ != null) {
				if (!elemVerticeI.getEtiqueta().equals(elemVerticeJ.getEtiqueta())){
					TVertice verticeI = (TVertice) elemVerticeI.getDatos();
					TVertice verticeJ = (TVertice) elemVerticeJ.getDatos();
					Integer costoAdyacencia =
							(Integer)verticeI.obtenerCostoAdyacencia(verticeJ);
					matrizCostos[i][j] = costoAdyacencia;
				}
				elemVerticeJ = (TElemento) elemVerticeJ.getSiguiente();
				j++;
			}
			elemVerticeI = (TElemento) elemVerticeI.getSiguiente();
			i++;
		}
		return matrizCostos;
	}
	
	public void mostrarMatriz(Integer[][] matrizCostos) {
		TElemento nodoActualListaVertices = (TElemento) vertices.obtenerPrimero();
		for (int i = 0; i < matrizCostos.length; i++) {
			TVertice verticeActual = (TVertice) nodoActualListaVertices.getDatos();
			StringBuffer cadenaFilaActual = new
					StringBuffer(verticeActual.etiqueta.toString());
			for (int j = 0; j < matrizCostos.length; j++) {
				if(matrizCostos[i][j]!=null){
					cadenaFilaActual.append(matrizCostos[i][j].toString());
				} else {
					cadenaFilaActual.append("----");
				}
				cadenaFilaActual.append('|');
			}
			System.out.println(cadenaFilaActual.toString());
			nodoActualListaVertices = (TElemento) nodoActualListaVertices.getSiguiente();
		}
		System.out.println("*********************");
	}*/

}
